package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转
* （例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 搜索螺旋排序数组_33 {
    public static void main(String[] args) {
        搜索螺旋排序数组_33 demo = new 搜索螺旋排序数组_33();
        int i = demo.search1(new int[]{
                4, 5, 6, 7, 0, 1, 2
        }, 0);
        System.out.println(i);
    }

    public int search(int[] nums, int target) {
        // 这他妈 你敢信？ 这就完事了？
        int result = -1;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == target){
                result = i;
                break;
            }
        }
        return result;
    }

    /*
    * 优化，利用升序的螺旋的特点
    * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/
    * 利用 二分 可以得知 mid 一定会落在 有序区间中   所以要判断 mid 是在哪一个有序区间中
    * 二分的话 一定会有一个有序区间 和一个无序的区间
    *  如何判断 ，因为 mid 是落在有序区间中的(无论螺旋点是哪个）
    * 所以当 nums[left] < nums[mid] 时，说明 left - mid 是有序的
    *  反之说明 mid-right 是有序的
    * */
    public int search1(int[] nums, int target) {
        int length = nums.length;
        int left = 0;
        int right = length-1;
        while(left<=right){
            int mid = (left+right) >> 1;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[left] <= nums[mid]){
                // 说明左半部分有序
                if(nums[left] <= target && target < nums[mid]){
                    right = mid-1;
                }else{
                    // 说明在右半部分
                    left = mid+1;
                }
            }else{
                // 说明右半部分有序
                if(nums[mid] < target && target <= nums[right]){
                    left = mid +1;
                }else{
                    right = mid-1;
                }
            }
        }
        return -1;
    }

}
